package fun.coding.leetcode;

public class RemoveNthNodeFromEndOfList {

	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		ListNode n1 = new ListNode(2);
		ListNode n2 = new ListNode(3);
		ListNode n3 = new ListNode(4);
		ListNode n4 = new ListNode(5);
		head.next = n1;
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = null;
		
		RemoveNthNodeFromEndOfList r = new RemoveNthNodeFromEndOfList();
		
		ListNode newHead = r.removeNthFromEnd(head, 5);
		
		ListNode iter = newHead;
		while (iter != null) {
			System.out.print(iter.val + ",");
			iter = iter.next;
		}
	}
	
	// Given linked list: 1->2->3->4->5, and n = 2.the linked list becomes 1->2->3->5.
	// Could also use dummy node, and two pointers
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode p = head;
		ListNode fast = head;
		
		for (int i = 0; i < n; i++) {
			fast = fast.next;
		}
		
		if (fast == null) return head.next;
		
		while (fast.next != null) {
			p = p.next;
			fast = fast.next;
		}
		
		p.next = p.next.next;
		
		return head;
    }

}
